package com.dyz.topics.dynamicProgramming;

public class LongestPalindrome5 {
    //0-1背包问题
    public int knapsck(int W, int N, int[]weights, int[]values) {
        //定义base case
        int[][] dp = new int[N+1][W+1];
        for(int i=1; i<=N; i++){
            int w=weights[i-1];//第i-1个物品的重量
            int v=values[i-1];//第i-1个物品的价值
            for(int j=1; j<=W;j++){
                if(j>=w){
                    dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-w]+v); //第i个物品放还是不放取最大
                }else{
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        return dp[N][W];
    }
    //完全背包问题
    public int CompleteBackpack(int W, int N, int[] weights, int[] values){
        //定义表达式
        int[][] dp = new int[N+1][W+1]; //从第一个开始，i=0号就是base case填充0， int默认为0，不要操作
        for(int i=1; i<=N; i++){
            int w = weights[i-1];
            int v = values[i-1];
            for(int j=1;j<=W;j++){
                //和01背包的区别就在这里，01背包只有两种状态：放与不放
                //而完全背包可以放0到k个物品i，同样是取最大值
                //因为是完全背包问题，所以第i-1个物品可以重复放，可以放j/w个物品
                int count = j/w;
                for(int k=0;k<=count; k++){
                    dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-k*w]+v*k);
                }
            }
        }
        return dp[N][W];
    }

    public static void main(String[] args) {
        int Value[] = {5,10,20};
        int weight[] = {3,2,2};
        int i = new LongestPalindrome5().CompleteBackpack(5, 3, weight, Value);
        System.out.println(i);
    }
}

